未分類

Intersection of Two Arrays II

BinarySearch, Go, HashTable, LeetCode, Sort, TwoPointers

Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

For Example:

1
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:

  • Each element in the result should appear as many times as it shows in both arrays.
  • The result can be in any order.

Follow up:

  • What if the given array is already sorted? How would you optimize your algorithm?
  • What if nums1’s size is small compared to nums2’s size? Which algorithm is better?
  • What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
提示 解題應用
HashTable HashMap

Default:

1
2
3
func intersect(nums1 []int, nums2 []int) []int {
}

解答思路:

這次需要你找出交集的部分，而且彼此都包含的部分可以重覆出現，所以這次在第一個陣列儲進hashmap時，key為元素值不變，而value改為儲存該元素出現的次數，到了第二個陣列要核對的只有該元素是否存在於hashmap之中，每核對完放入結果時該數的次數就要-1，至於兩陣列如果值能重覆都需有相同最大數量就看是hashmap的數量先歸0，還是第二個陣列的核對先結束來決定。

針對Follow Up的部分前1,2點如果是用HashMap來處理就不會有區別，而第三點如果是nums2沒辦法完全放入記憶體之中的話，就是先把第一個陣列放入hashmap之中，正好就是上述思路的做法，然後再批次到硬碟讀取nums2的資料來處理。

程式碼解說:

一樣初始化一空陣列用於回傳結果，hashmap的value改儲存次數所以為int的型別，在第一個陣列用迴圈完全倒入hashmap之後，接著便是第二個陣列利用迴圈開始一一核對，如果該元素在hashmap存在且儲存的數量尚未歸0就放入結果之中同時將次數-1，如果該數的次數先歸0，表示在第一個陣列最多只能交集這些數量，反之尚未歸0而第二個陣列的核對已經結束了，表示第二個陣列最多只能交集這些數量，最後在核對結束之後將結果回傳

1
2
3
4
5
6
7
8
9
10
11
12
13
result := []int{}
hashMap := make(map[int]int)
for _, v := range nums1 {
	hashMap[v] += 1
}
for _, v := range nums2 {
	amount, ok := hashMap[v]
	if ok && amount > 0 {
		result = append(result, v)
		hashMap[v] -= 1
	}
}
return result

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func intersect(nums1 []int, nums2 []int) []int {
	result := []int{}
	hashMap := make(map[int]int)
	for _, v := range nums1 {
		hashMap[v] += 1
	}
	for _, v := range nums2 {
		amount, ok := hashMap[v]
		if ok && amount > 0 {
			result = append(result, v)
			hashMap[v] -= 1
		}
	}
	return result
}

總結:

如果需要找出兩陣列所交集的部分，且需包含重覆且相同的最大數量，此時在第一個陣列儲進hashmap時，key為元素值，而value改為儲存該元素出現的次數，到了第二個陣列要核對的只有該元素是否存在於hashmap之中，每核對完放入結果時該數的次數就要-1，最後重覆且相同的最大數量就看是hashmap的數量先歸0，還是第二個陣列的核對先結束來決定

分享到